// Copyright (c) 2006, Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//
// Author: arvin.chen
//
//

#ifndef ALGORITHM_SORT_QUICK_H_
#define ALGORITHM_SORT_QUICK_H_
#include <stack>

#ifndef ALGORITHM_SORT_BASE_H_
#include "algorithm/sort/base.h"
#endif

namespace algorithm {
	namespace sort {
		
		template<typename T>
		class Quick : public Base<T> {
		public:

			/**
			* Construction
			*
			* @param
			* @return
			*/
			Quick() :
				Base<T>::Base(kQuick)
			{
				
			}

			/**
			* Destruction
			*
			* @param VOID
			* @return
			*/
			~Quick()
			{

			}

			/**
			* sort
			*
			* @param T arr[]
			* @param int len
			* @return T
			*/
			virtual T* sort(T arr[], int len)
			{
				if (nullptr == arr || 1 >= len) return arr;
				//The recursive algorithm is mainly to divide sub - intervals.If you want to achieve fast sorting without recursion, you only need to use a stack to save the interval.
				//Generally, the first thing that comes to mind when changing a recursive program to non - recursive is to use the stack, because recursion itself is a process of pushing the stack.
				int left = 0;
				int right = len - 1;
				std::stack<int> statck_pos;
				statck_pos.push(left);
				statck_pos.push(right);//Right after entering, so take right first
				while (!statck_pos.empty()) {
					int right = statck_pos.top();
					statck_pos.pop();
					int left = statck_pos.top();
					statck_pos.pop();

					int index = QuickArr(arr, left, right);
					if ((index - 1) > left) {
						statck_pos.push(left);
						statck_pos.push(index - 1);
					}
					if ((index + 1) < right) {
						statck_pos.push(index + 1);
						statck_pos.push(right);
					}
				}
				return arr;
			}

		protected:
			/**
			* Assignment
			*
			* @param const Quick& cbase
			* @return Quick&
			*/
			Quick& operator=(const Quick& cbase);

			/**
			* Copy Construction
			*
			* @param const Quick& cbase
			* @return
			*/
			Quick(const Quick& cbase);

		private:


			/**
			* QuickArr
			* Get the position of the axis element
			*
			* @param T arr[]
			* @param int h
			* @param int i
			* @return int
			*/
			int QuickArr(T arr[], int left, int right) {
				T pivot = arr[left];
				int i = left + 1;
				int j = right;
				while (true) {
					// Find the first element position less than or equal to pivot to the right
					while (i <= j && arr[i] <= pivot) i++;
					// Find the first element position greater than or equal to pivot to the left
					while(i <= j && arr[j] >= pivot ) j--;
					if(i >= j)
						break;
					//Exchange the positions of the two elements so that the element on the left is not greater than pivot, and the one on the right is not less than pivot
					std::swap(arr[i], arr[j]);
// 					T temp = arr[i];
// 					arr[i] = arr[j];
// 					arr[j] = temp;
				}
				// Make the central axis elements in an orderly position
				std::swap(arr[left], arr[j]);
// 				arr[left] = arr[j];
// 				arr[j] = pivot;
				return j;
			}

		public:
		protected:
		private:

		};
	} // namespace algorithm 
} // namespace sort


#endif  // ALGORITHM_SORT_QUICK_H_
